package com.cbd.basic.leetcode.easy;

import lombok.extern.slf4j.Slf4j;

/**
 * 回文数
 */
@Slf4j
public class Solution9 {
    public static void main(String[] args) {
        int x = 1221;
        boolean result = isPalindrome(x);
        log.info("result = {}", result);
    }

    /**
     * 时间复杂度：O(log n)，每次迭代都是除以10
     * 空间复杂度：O(1)
     */
    public static boolean isPalindrome(int x) {
        // 负数不可能是回文数，最后一位是0的肯定不是回文数
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }
        // 数字 % 10 = 最后一位，数字 / 10 = 数字除去最后一位
        // 回文数 = 回文数 * 10 + 最后一位
        // 数字折半，反转后一半，和前一半比较，数字位数是奇数，后一半反转 / 10 = 前一半，数字位数是偶数，后一半反转 = 前一半
        // 折半逻辑，原始数字 <= 反转后一半数字
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x = x / 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
}
